Termination w.r.t. Q proof of TRS/Rubioma96.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

Q is empty.

↳ QTRS

  ↳ Overlay + Local Confluence

Q restricted rewrite system:
The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

Q is empty.

The TRS is overlay and locally confluent. By [15] we can switch to innermost.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

EQ(var(L), var(Lp)) → EQ(L, Lp)
REN(X, Y, apply(T, S)) → REN(X, Y, T)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(T, Tp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(X, Xp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → AND(eq(T, Tp), eq(S, Sp))
EQ(cons(T, L), cons(Tp, Lp)) → EQ(T, Tp)
REN(var(L), var(K), var(Lp)) → EQ(L, Lp)
EQ(lambda(X, T), lambda(Xp, Tp)) → AND(eq(T, Tp), eq(X, Xp))
EQ(cons(T, L), cons(Tp, Lp)) → AND(eq(T, Tp), eq(L, Lp))
REN(X, Y, lambda(Z, T)) → REN(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T))
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(T, Tp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(S, Sp)
REN(var(L), var(K), var(Lp)) → IF(eq(L, Lp), var(K), var(Lp))
REN(X, Y, lambda(Z, T)) → REN(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)
REN(X, Y, apply(T, S)) → REN(X, Y, S)

The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

EQ(var(L), var(Lp)) → EQ(L, Lp)
REN(X, Y, apply(T, S)) → REN(X, Y, T)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(T, Tp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(X, Xp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → AND(eq(T, Tp), eq(S, Sp))
EQ(cons(T, L), cons(Tp, Lp)) → EQ(T, Tp)
REN(var(L), var(K), var(Lp)) → EQ(L, Lp)
EQ(lambda(X, T), lambda(Xp, Tp)) → AND(eq(T, Tp), eq(X, Xp))
EQ(cons(T, L), cons(Tp, Lp)) → AND(eq(T, Tp), eq(L, Lp))
REN(X, Y, lambda(Z, T)) → REN(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T))
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(T, Tp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(S, Sp)
REN(var(L), var(K), var(Lp)) → IF(eq(L, Lp), var(K), var(Lp))
REN(X, Y, lambda(Z, T)) → REN(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)
REN(X, Y, apply(T, S)) → REN(X, Y, S)

The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

REN(X, Y, apply(T, S)) → REN(X, Y, T)
EQ(var(L), var(Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(T, Tp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(X, Xp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → AND(eq(T, Tp), eq(S, Sp))
EQ(cons(T, L), cons(Tp, Lp)) → EQ(T, Tp)
REN(var(L), var(K), var(Lp)) → EQ(L, Lp)
EQ(lambda(X, T), lambda(Xp, Tp)) → AND(eq(T, Tp), eq(X, Xp))
EQ(cons(T, L), cons(Tp, Lp)) → AND(eq(T, Tp), eq(L, Lp))
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(T, Tp)
REN(X, Y, lambda(Z, T)) → REN(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T))
EQ(apply(T, S), apply(Tp, Sp)) → EQ(S, Sp)
REN(var(L), var(K), var(Lp)) → IF(eq(L, Lp), var(K), var(Lp))
REN(X, Y, apply(T, S)) → REN(X, Y, S)
REN(X, Y, lambda(Z, T)) → REN(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)

The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 5 less nodes.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

EQ(var(L), var(Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(T, Tp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(X, Xp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(L, Lp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(T, Tp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(S, Sp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(T, Tp)

The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

EQ(var(L), var(Lp)) → EQ(L, Lp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(T, Tp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(X, Xp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(L, Lp)
EQ(lambda(X, T), lambda(Xp, Tp)) → EQ(T, Tp)
EQ(apply(T, S), apply(Tp, Sp)) → EQ(S, Sp)
EQ(cons(T, L), cons(Tp, Lp)) → EQ(T, Tp)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
EQ(x1, x2) = x2
var(x1) = var(x1)
apply(x1, x2) = apply(x1, x2)
lambda(x1, x2) = lambda(x1, x2)
cons(x1, x2) = cons(x1, x2)

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ PisEmptyProof

                  ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

REN(X, Y, apply(T, S)) → REN(X, Y, T)
REN(X, Y, lambda(Z, T)) → REN(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T))
REN(X, Y, lambda(Z, T)) → REN(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)
REN(X, Y, apply(T, S)) → REN(X, Y, S)

The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

REN(X, Y, apply(T, S)) → REN(X, Y, T)
REN(X, Y, lambda(Z, T)) → REN(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T))
REN(X, Y, lambda(Z, T)) → REN(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)
REN(X, Y, apply(T, S)) → REN(X, Y, S)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
REN(x1, x2, x3) = x3
apply(x1, x2) = apply(x1, x2)
lambda(x1, x2) = lambda(x1, x2)
ren(x1, x2, x3) = x3
var(x1) = var
cons(x1, x2) = x1
nil = nil
if(x1, x2, x3) = x2
true = true
and(x1, x2) = x2
false = false
eq(x1, x2) = x1

Recursive Path Order [2].
Precedence:

apply₂ > var
lambda₂ > var
nil > var
true > var
false > var

The following usable rules [14] were oriented:

if(true, var(K), var(L)) → var(K)
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))

The set Q consists of the following terms:

and(false, false)
and(true, false)
and(false, true)
and(true, true)
eq(nil, nil)
eq(cons(x0, x1), nil)
eq(nil, cons(x0, x1))
eq(cons(x0, x1), cons(x2, x3))
eq(var(x0), var(x1))
eq(var(x0), apply(x1, x2))
eq(var(x0), lambda(x1, x2))
eq(apply(x0, x1), var(x2))
eq(apply(x0, x1), apply(x2, x3))
eq(apply(x0, x1), lambda(x2, x3))
eq(lambda(x0, x1), var(x2))
eq(lambda(x0, x1), apply(x2, x3))
eq(lambda(x0, x1), lambda(x2, x3))
if(true, var(x0), var(x1))
if(false, var(x0), var(x1))
ren(var(x0), var(x1), var(x2))
ren(x0, x1, apply(x2, x3))
ren(x0, x1, lambda(x2, x3))

We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.